/*
 *	  CSC 501 - HW5 sample code
 */

#include <arpa/inet.h>
#include <netinet/in.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <stdlib.h>
#include <openssl/md5.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <netdb.h>
#include <errno.h>
#include <math.h>

#define BUFLEN 512
#define VALUE_LEN 20
#define HASH_LEN 16
#define IPPORT_LEN 20

int TOTAL_NODES;
int portnum = 50000;

/* Node pointer typedef that is used to point to the next and previous pointers */
typedef struct node *nodeptr;

/**
 * Node type for doubly linked list 
 * each entry has a pointer to previous
 * node in the list, and next node in the list
 *
 * Each of these node_t structures represents a finger table entry and key, value pair
 */
typedef struct node {
    char ipPort[IPPORT_LEN];
	char portHash[HASH_LEN];
	char key[VALUE_LEN];
	char value[VALUE_LEN];
} node_t;

node_t fingerTable[10];

int lgN;
int fingersInitialized = 0;
int successors = 0;
int valuePairs = 0;

char putKey[VALUE_LEN] = "";
int samePutCount = 0;
char getKey[VALUE_LEN] = "";
int sameGetCount = 0;

void initialize_fingers(void);
int compareKeyNode(char *, char *);
void printFingerTable(void);
void printValueTable(void);

void printhash(unsigned char h[HASH_LEN])
{	 int i;
	 for(i=0;i<HASH_LEN;i++)
		 printf("%02x",h[i]);
}

/*
 *  calculates the hash and stores in h
 */
void calculatehash(char *c, int len, char *h)
{	MD5(c,len, h);
}

/*
 * forwards message m to port
 */
void forward_message(int port, char *m)
{
		struct sockaddr_in sock_client;
		struct hostent *hent;
		int sc, i, slen = sizeof(sock_client);

		if ((sc = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
			printf("socket creation failed ");
			exit(1);
		}

		hent = gethostbyname("localhost");
		if(hent == NULL)
		{	printf("gethostbyname failed ");
			exit(1);
		}

		memset((char *) &sock_client, 0, sizeof(sock_client));

		sock_client.sin_family = AF_INET;
		sock_client.sin_port = htons(port);
		sock_client.sin_addr = *(struct in_addr*)(hent ->h_addr_list[0]);

		if (connect(sc, (struct sockaddr *) &sock_client, slen) == -1) {
			printf("connect failed");
			exit(1);
		}

		if (send(sc, m, BUFLEN, 0) == -1) {
			printf("send failed ");
			exit(1);
		}
		close(sc);
}

void server_listen() {
	struct sockaddr_in sock_server, sock_client;
	int s, slen = sizeof(sock_client);
	char *command;
	char buf[BUFLEN];
	int client;

	if ((s = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
		printf("error in socket creation");
		exit(1);
	}

	memset((char *) &sock_server, 0, sizeof(sock_server));
	sock_server.sin_family = AF_INET;
	sock_server.sin_port = htons(portnum);
	sock_server.sin_addr.s_addr = htonl(INADDR_ANY);
	if (bind(s, (struct sockaddr *) &sock_server, sizeof(sock_server)) == -1) {
		printf("error in binding socket");
		exit(1);
	}

	if (listen(s, 10) == -1) {
		printf("listen error");
		exit(1);
	}

	char nodehash_string[IPPORT_LEN], hash[HASH_LEN];

	sprintf(nodehash_string,"localhost%d",portnum);
	calculatehash(nodehash_string, strlen(nodehash_string), hash);

	printf("DHT node (");
	printhash(hash);
	printf("): Listening on port number %d . . . \n", portnum);

	while (1) { /* quit only on END message */
		if ((client = accept(s, (struct sockaddr *) &sock_client, &slen)) == -1) {
			printf("accept error");
			exit(1);
		}

		if (recv(client, buf, BUFLEN, 0) == -1) {
			printf("recv error");
			exit(1);
		}

		command = strtok(buf, ":");	
		if (strcmp(command, "END") == 0) {
			FILE *file = NULL;
			if((file = fopen("nodelist","a+")) == NULL){
				perror("Failed to open nodelist file!");
			}
			
			int numX = 0, i;
			char countingTest[IPPORT_LEN];
			char *retString;
			for(i = 0;i < TOTAL_NODES;i++){
				retString = fgets(countingTest, IPPORT_LEN, file);
			}
			
			while((retString = fgets(countingTest, IPPORT_LEN, file)) != NULL){
				numX++;
			}
			
			if(numX == (TOTAL_NODES - 1)){
				fclose(file);
				if(remove("nodelist") == -1){
					printf("Could not delete nodelist file!\n");
				}
				
				break;
			} else{
				if(fprintf(file, "%c\n", 'X') <= 0){
					perror("Failed to append X to nodelist file!");
				}
				fclose(file);
						
				int i, port = 0;
				char *portString = fingerTable[0].ipPort;			
				for(portString = portString + 10;*portString != '\n';portString++){
					port = port * 10 + (*portString - '0');
				}
			
				forward_message(port, command);
			
				close(client);
			
				break;
			}
		} else if (strcmp(command, "PUT") == 0) {
			char *key = strtok(NULL, ":");
			char *value = strtok(NULL, ":");
			
			char keyHash[HASH_LEN];
			calculatehash(key, strlen(key), keyHash);
			
			if(strcmp(key, putKey) != 0){
				strcpy(putKey, key);
				samePutCount = 0;
			} else{
				if(samePutCount >= 2){
					printf("Cannot put this key, all nodes contain lgN entries!\n");
					continue;
				}
				
				if(valuePairs == lgN){
					int m, pNum = 0;
					for(m = 10;fingerTable[0].ipPort[m] != '\n';m++){
						pNum = pNum * 10 + (fingerTable[0].ipPort[m] - '0');
					}
					
					char fwdMess[45];
					sprintf(fwdMess,"%s:%s:%s", command, key, value);
					
					forward_message(pNum, fwdMess);
					
					printf("PUT for %s [", key);
					printhash(keyHash);
					printf("] was forwarded to localhost:%d\n", pNum);
				} else{
					strcpy(fingerTable[valuePairs].key, key);
					strcpy(fingerTable[valuePairs].value, value);
					valuePairs++;
					
					printf("(key:value) = (%s [", key);
					printhash(keyHash);
					printf("] : %s) inserted\n", value);
				}
				
				samePutCount++;
				continue;
			}
			
			int diffWithCurrent = compareKeyNode(keyHash, hash);
			
			int succIndex = 0, diff, closestSucc = 0, diffWithSucc = compareKeyNode(keyHash, fingerTable[succIndex].portHash);
			for(succIndex = 1;succIndex < successors;succIndex++){
				diff = compareKeyNode(keyHash, fingerTable[succIndex].portHash);
				if(diff < diffWithSucc){
					diffWithSucc = diff;
					closestSucc = succIndex;
				}
			}
			
			if(diffWithCurrent <= diffWithSucc){
				if(valuePairs == lgN){
					int m, pNum = 0;
					for(m = 10;fingerTable[closestSucc].ipPort[m] != '\n';m++){
						pNum = pNum * 10 + (fingerTable[closestSucc].ipPort[m] - '0');
					}
					
					char fwdMess[45];
					sprintf(fwdMess,"%s:%s:%s", command, key, value);
					
					forward_message(pNum, fwdMess);
					
					printf("PUT for %s [", key);
					printhash(keyHash);
					printf("] was forwarded to localhost:%d\n", pNum);
				} else{
					strcpy(fingerTable[valuePairs].key, key);
					strcpy(fingerTable[valuePairs].value, value);
					valuePairs++;
					
					printf("(key:value) = (%s [", key);
					printhash(keyHash);
					printf("] : %s) inserted\n", value);
				}
			} else {
				int m, pNum = 0;
				for(m = 10;fingerTable[closestSucc].ipPort[m] != '\n';m++){
					pNum = pNum * 10 + (fingerTable[closestSucc].ipPort[m] - '0');
				}
				
				char fwdMess[45];
				sprintf(fwdMess,"%s:%s:%s", command, key, value);
				
				forward_message(pNum, fwdMess);
				
				printf("PUT for %s [", key);
				printhash(keyHash);
				printf("] was forwarded to localhost:%d\n", pNum);
			}
			
			samePutCount++;
		} else if (strcmp(command, "GET") == 0) {
			sleep(1);
		
			char *key = strtok(NULL, ":");
			
			char keyHash[HASH_LEN];
			calculatehash(key, strlen(key), keyHash);
			
			if(strcmp(key, getKey) != 0){
				strcpy(getKey, key);
				sameGetCount = 0;
			} else{
				if(sameGetCount >= 2){
					printf("Cannot get this key, does not exist!\n");
					forward_message(65534, "QUIT");
					continue;
				}
				
				int valueIndex, found = 0;
				for(valueIndex = 0;valueIndex < valuePairs;valueIndex++){
					if(strcmp(fingerTable[valueIndex].key,key) == 0){
						printf("Found key value pair (%s:%s)\n\n", key, fingerTable[valueIndex].value);
						
						char foundMess[50];
						sprintf(foundMess,"Found %s:%s", key, fingerTable[valueIndex].value);
						
						close(client);
						forward_message(65534, foundMess);
						
						found = 1;
					}
				}
				
				if(!found){
					int m, pNum = 0;
					for(m = 10;fingerTable[0].ipPort[m] != '\n';m++){
						pNum = pNum * 10 + (fingerTable[0].ipPort[m] - '0');
					}
					
					char fwdMess[45];
					sprintf(fwdMess,"%s:%s", command, key);
					
					forward_message(pNum, fwdMess);
					
					printf("GET for %s [", key);
					printhash(keyHash);
					printf("] was forwarded to localhost:%d\n", pNum);
				}
				
				sameGetCount++;
				continue;
			}
			
			int diffWithCurrent = compareKeyNode(keyHash, hash);
			
			int succIndex = 0, diff, closestSucc = 0, diffWithSucc = compareKeyNode(keyHash, fingerTable[succIndex].portHash);
			for(succIndex = 1;succIndex < successors;succIndex++){
				diff = compareKeyNode(keyHash, fingerTable[succIndex].portHash);
				if(diff < diffWithSucc){
					diffWithSucc = diff;
					closestSucc = succIndex;
				}
			}
			
			if(diffWithCurrent <= diffWithSucc){
				int valueIndex, found = 0;
				for(valueIndex = 0;valueIndex < valuePairs;valueIndex++){
					if(strcmp(fingerTable[valueIndex].key,key) == 0){
						printf("Found key value pair (%s:%s)\n\n", key, fingerTable[valueIndex].value);
						
						char foundMess[50];
						sprintf(foundMess,"Found %s:%s", key, fingerTable[valueIndex].value);
						
						close(client);
						forward_message(65534, foundMess);
						
						found = 1;
					}
				}
				
				if(!found){
					int m, pNum = 0;
					for(m = 10;fingerTable[closestSucc].ipPort[m] != '\n';m++){
						pNum = pNum * 10 + (fingerTable[closestSucc].ipPort[m] - '0');
					}
					
					char fwdMess[45];
					sprintf(fwdMess,"%s:%s", command, key);
					
					forward_message(pNum, fwdMess);
					
					printf("GET for %s [", key);
					printhash(keyHash);
					printf("] was forwarded to localhost:%d\n", pNum);
				}
			} else {
				int m, pNum = 0;
				for(m = 10;fingerTable[closestSucc].ipPort[m] != '\n';m++){
					pNum = pNum * 10 + (fingerTable[closestSucc].ipPort[m] - '0');
				}
				
				char fwdMess[45];
				sprintf(fwdMess,"%s:%s", command, key);
				
				forward_message(pNum, fwdMess);
				
				printf("GET for %s [", key);
				printhash(keyHash);
				printf("] was forwarded to localhost:%d\n", pNum);
			}
			
			sameGetCount++;
		} else if (strcmp(command, "QUERY") == 0) {
			printValueTable();
		} else if (strcmp(command, "START") == 0){
			if(fingersInitialized == 0){
				initialize_fingers();
			}
		}
		close(client);
	}

	close(s);
}

void initialize_host(){
		/* Get random port number and build string localhost+port */
		srand((unsigned)(time(0)));
		portnum = 1025 + (int) abs(((65533 * rand()) % (64508)));
		
		/* Try to open file nodelist:  if success, then count lines and check against N-1, then add your own line */
		FILE *nodeList;
		if((nodeList = fopen("nodelist","a+")) == NULL){
			perror("Failed to open nodelist file!");
		}
		
		char node_string[IPPORT_LEN];
		sprintf(node_string, "localhost:%d", portnum);
		
		if(fprintf(nodeList, "%s\n", node_string) <= 0){
			perror("Failed to append hostname:portnum to nodelist file!");
		}
		
		fseek(nodeList, 0L, SEEK_SET);
		
		int numLines = 0;
		char countingTest[IPPORT_LEN];
		char *retString;
		while((retString = fgets(countingTest, IPPORT_LEN, nodeList)) != NULL){
			numLines++;
		}
		
		if(fclose(nodeList) != 0){
			perror("Failed to close nodelist file!");
		}
		
		/* If I found numLines to be N then I need to initialize my finger table and send START message */
		if(numLines == TOTAL_NODES){
			initialize_fingers();
		}
}

int sendStartMsg(int pNum){
	struct sockaddr_in sr;
	int s, i, slen = sizeof(sr);
	char buf[6] = "START\0";
	struct hostent *hent;

	int port = pNum;

	hent = gethostbyname("localhost");
	if(hent == NULL)
	{	printf("gethostbyname failed ");
		exit(1);
	}

	if ((s = socket(AF_INET, SOCK_STREAM, 0)) == -1) {}

	memset((char *) &sr, 0, sizeof(sr));
	sr.sin_family = AF_INET;
	sr.sin_port = htons(port);
	sr.sin_addr = *(struct in_addr*)(hent ->h_addr_list[0]);

	if (connect(s, (struct sockaddr *) &sr, sizeof(sr)) == -1) {
		printf("connect error");
		exit(1);
	}

	/* send a message to the server PORT on machine HOST */
	if (send(s, buf, 6, 0) == -1) {
		printf("send error");
		exit(1);
	}

	close(s);
	return 0;
}

void initialize_fingers(){
	/* Get each line of nodelist and create hash ID for each localhostPortnum and store in finger table */
	FILE *nodeList;
	if((nodeList = fopen("nodelist","r")) == NULL){
		perror("Failed to open nodelist file!");
	}
	
	/* Search file for my portnum to use as starting place for finger initialization */
	char hostPort[IPPORT_LEN];
	char *retString;
	while((retString = fgets(hostPort, IPPORT_LEN, nodeList)) != NULL){
		int i, port = 0;
		for(i = 10;hostPort[i] != '\n';i++){
			port = port * 10 + (hostPort[i] - '0');
		}
		
		if(port == portnum){
			break;
		}
	}
	
	/* Now we need to read in the fingers from the appropriate locations in the file, based on finger[i] = n + 2^(i-1) */
	int j, offset, linesToRead = 0, linesRead = 0, fingersAdded = 0, firstSucPort = 0, index = 0;
	for(j = 1;fingersAdded < lgN;j++){
		offset = pow(2, (j - 1));
		linesToRead = offset - linesRead;
		
		for(;linesToRead > 0;linesToRead--){
			retString = fgets(hostPort, 20, nodeList);
			
			if(retString == NULL){
				fseek(nodeList, 0L, SEEK_SET);
				linesToRead++;
				continue;
			}
			
			if(linesToRead == 1){
				/* Get portnum of this successor */
				int k, portN = 0;
				for(k = 10;hostPort[k] != '\n';k++){
					portN = portN * 10 + (hostPort[k] - '0');
				}
				
				if(j == 1){
					firstSucPort = portN;
				}
			
				/* Calculate hash ID for this successor */
				char nodehash_string[IPPORT_LEN], hash[HASH_LEN];
				sprintf(nodehash_string,"localhost%d",portN);
				calculatehash(nodehash_string, strlen(nodehash_string), hash);
				
				node_t new;
				strcpy(new.ipPort, retString);
				strcpy(new.portHash, hash);
				fingerTable[index] = new;
				
				index++;
				successors++;
			}
			
			linesRead++;
		}
		
		fingersAdded++;
	}
	
	if(fclose(nodeList) != 0){
		perror("Failed to close nodelist file!");
	}
	
	/* Set fingersInitialized = 1 now that your finger table is complete */
	fingersInitialized = 1;
	
	/* Send START message to first entry in my finger table */
	sendStartMsg(firstSucPort);
}

int main(int argc, char *argv[]) {

	if (argc != 2) {
		printf("wrong number of arguments");
		return;
	}

	TOTAL_NODES = atoi(argv[1]);
	
	/* Calculate log base 2 of N */
	double logBase10 = log10((double) TOTAL_NODES);
	double log2N = logBase10 / log10((double) 2);
	lgN = (int) log2N;

	initialize_host();
	server_listen();

	return 0;
}

int compareKeyNode(char *keyHash, char *nodeHash){
	int i, hashDifference = 0;
	for(i=0;i < HASH_LEN;i++){
		hashDifference += abs((int) keyHash[i] - (int) nodeHash[i]);
	}
	
	return hashDifference;
}

/**
 * Print contents of finger table
 *
 * \return nothing
*/
void printFingerTable(){
	printf("Number of fingers is: %d\n", successors);
	
	/* Increment list printing each finger info */
	int index;
	for(index = 0;index < successors;index++){
		printf("\nFinger %d: Hostname:PortNum is: %s", index, fingerTable[index].ipPort);
		printf("Finger %d: Hash ID is: ", index);
		printhash(fingerTable[index].portHash);
		printf("\n\n");
	}
}

/**
 * Print contents of value table
 *
 * \return nothing
*/
void printValueTable(){
	printf("\nKey                 Value               \n");
	printf("----------------------------------------\n");
	
	/* Increment list printing each key-value pair */
	int index;
	for(index = 0;index < valuePairs;index++){
		printf("%-20s", fingerTable[index].key);
		printf("%-20s\n", fingerTable[index].value);
	}
	
	printf("----------------------------------------\n\n");
}
